package Leetcode;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    class ListNode {
        int val;
        ListNode next;
        ListNode pre;
        ListNode(int x) {
            val = x;
            next = null;
            pre = null;
        }
        ListNode(int x, ListNode node) {
            val = x;
            this.next = node;
        }
        ListNode(int x, ListNode pre, ListNode next) {
            val = x;
            this.pre = pre;
            this.next = next;
        }
    }

    int Length = 0;
    ListNode head = null;
    ListNode tail = null;
    int size = 0;
    Map<Integer, ListNode> map = new HashMap<>();
    public LRUCache(int capacity) {
        this.Length = capacity;
        head = new ListNode(-1);
        tail = new ListNode(-1);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (map.containsKey(key)){
            ListNode node = map.get(key);
            moveToHead(node);
            return node.val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)){
            ListNode newNode = new ListNode(value);
            addHead(newNode);
            map.put(key, newNode);
            size++;
            if (size > Length){
                map.remove(removeTail().val);
                size--;
            }
        } else {
            ListNode node = map.get(key);
            node.val = value;
            moveToHead(node);
        }
    }
    public void addHead(ListNode newNode){
        if (tail.pre == head){
            newNode.pre = head;
            newNode.next = tail;
            head.next = newNode;
            tail.pre = newNode;
        } else {
            newNode.pre = head;
            newNode.next = head.next;
            head.next.pre = newNode;
            head.next = newNode;
        }
    }
    public void moveToHead(ListNode node){
        removeNode(node);
        addHead(node);
    }
    public void removeNode(ListNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    public ListNode removeTail(){
        ListNode pre = tail.pre;
        removeNode(pre);
        return pre;
    }
}
